Over the past decade, traditional database techniques were found inadequate to completely address the needs of domain-specific applications. To this end, domain-specific extensions like spatial, text, XML, or genetic databases have been designed to cater to the specific needs of the industry and have been proven quite successful. Most research in databases has consequently been focused on addressing the idiosyncrasies of these domain applications by using, and extending existing database technology or inventing novel database techniques. Indexing of domain data to cater to domain specific queries is one such area that has received much attention. Spatial researchers proposed many efficient indexes for storage and retrieval of spatial data in databases. The text community has devised new and efficient indexes for text data. XML researchers have proposed new structures for searching on the tree structure semantics of XML documents.
Efficient update algorithms for domain indexes have also been proposed. These include insertion, deletion in bulk, sub tree merging, buffering-based updates, etc. Most of these proposals consider the operations in isolation. Other proposals study and propose new concurrency models for domain indexes.
The problem of incorporating transactional updates in hierarchical spatial indexes like R-trees has also received much attention in research. R-trees have a hierarchical tree structure. Each node of the tree is stored as a row in an index table. The leaf-level of the R-tree stores pointers to rows of a user table that is indexed by the R-tree. A problem arises if updates to user table are incorporated as part of the user transaction, since the updates may conflict at the R-tree node level even if the underlying updates from two different transactions do not conflict. This could lead to deadlocks even when the transactions do not conflict if the index were not to be there.
A need arises for a technique by which updates may be incorporated in Spatial R-tree indexes without causing deadlocks of user transactions.